package 数组题目.数组求和;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//和四数之和
//https://leetcode.cn/problems/4sum/description/
class 四数之和 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        // 数组长度不足4，直接返回空结果
        if (nums == null || nums.length < 4) {
            return result;
        }
        // 排序便于去重和双指针操作
        Arrays.sort(nums);
        // 遍历第一个数
        for (int i = 0; i < nums.length - 3; i++) {
            // 跳过重复的第一个数
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 递归寻找剩下的三个数
            List<List<Integer>> threeSumResults = threeSum(nums, i + 1, target - nums[i]);
            for (List<Integer> triplet : threeSumResults) {
                // 将当前数加入三元组，形成四元组
                triplet.addFirst(nums[i]);
                result.add(triplet);
            }
        }

        return result;
    }

    /**
     * 在nums数组中，从startIndex开始寻找所有不重复的三元组，使其和为target
     */
    private List<List<Integer>> threeSum(int[] nums, int startIndex, long target) {
        List<List<Integer>> result = new ArrayList<>();

        // 遍历第二个数
        for (int i = startIndex; i < nums.length - 2; i++) {
            // 跳过重复的第二个数
            if (i > startIndex && nums[i] == nums[i - 1]) {
                continue;
            }

            // 寻找剩下的两个数
            List<List<Integer>> twoSumResults = twoSum(nums, i + 1, target - nums[i]);
            for (List<Integer> pair : twoSumResults) {
                // 将当前数加入二元组，形成三元组
                pair.addFirst(nums[i]);
                result.add(pair);
            }
        }

        return result;
    }

    /**
     * 在nums数组中，从startIndex开始到末尾，寻找所有不重复的二元组，使其和为target
     */
    private List<List<Integer>> twoSum(int[] nums, int startIndex, long target) {
        List<List<Integer>> result = new ArrayList<>();
        int left = startIndex;
        int right = nums.length - 1;

        // 双指针寻找符合条件的两个数
        while (left < right) {
            int leftVal = nums[left];
            int rightVal = nums[right];
            long sum = (long) leftVal + rightVal;

            if (sum == target) {
                // 找到符合条件的一对数
                List<Integer> pair = new ArrayList<>();
                pair.add(leftVal);
                pair.add(rightVal);
                result.add(pair);

                // 跳过重复的左值
                while (left < right && nums[left] == leftVal) {
                    left++;
                }
                // 跳过重复的右值
                while (left < right && nums[right] == rightVal) {
                    right--;
                }
            } else if (sum < target) {
                // 和小于目标值，左指针右移
                left++;
            } else {
                // 和大于目标值，右指针左移
                right--;
            }
        }

        return result;
    }
}
